#define _CRT_SECURE_NO_WARNINGS 1

class MagicDictionary
{
    struct DictTreeNode
    {
        std::vector<DictTreeNode*> _sub;
        bool _end;

        DictTreeNode()
            : _sub(26, nullptr)
            , _end(false)
        { }
    };

public:
    /** Initialize your data structure here. */
    MagicDictionary()
        : _root(new DictTreeNode())
    { }

    void buildDict(vector<string> dictionary)
    {
        for (const auto& str : dictionary)
        {
            DictTreeNode* cur = _root;
            for (char c : str)
            {
                if (cur->_sub[c - 'a'] == nullptr)
                {
                    cur->_sub[c - 'a'] = new DictTreeNode();
                }
                cur = cur->_sub[c - 'a'];
            }

            cur->_end = true;
        }
    }

    bool search(string searchWord)
    {
        return _search(searchWord, _root, 0, 0);
    }

private:
    bool _search(const std::string& searchWord, DictTreeNode* cur, size_t index, int change)
    {
        if (change == 2) {
            return false;
        }

        if (index == searchWord.size()) {
            return change == 1 && cur->_end;
        }

        if (cur->_sub[searchWord[index] - 'a'] &&
            _search(searchWord, cur->_sub[searchWord[index] - 'a'], index + 1, change))
        {
            return true;
        }

        for (int i = 0; i < 26; ++i)
        {
            if (cur->_sub[i] != nullptr && i != searchWord[index] - 'a')
            {
                bool ret = _search(searchWord, cur->_sub[i], index + 1, change + 1);
                if (ret == true) {
                    return true;
                }
            }
        }

        return false;
    }

    DictTreeNode* _root;
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */